package com.ayuer.chapter02;

import java.util.Arrays;

public class AlgoClimbDemo {

    /**
     * 分解子问题
     *
     * @return
     */
    public static int climb(int n, int[] cache) {
        if (cache[n] != -1) {
            return cache[n];
        }
        if (n == 2) {
            return 2;
        }
        if (n == 1) {
            return 1;
        }
        int result = climb(n - 1, cache) + climb(n - 2, cache);
        cache[result] = 1;
        return result;
    }

    public static void main(String[] args) {


        int[] cache = new int[100];
        Arrays.fill(cache, -1);
        //求第n阶梯
        int climb = climb(4, cache);
        System.out.println(climb);
    }
}
